// 给定一个非负整数 N，找出小于或等于 N 的最大的整数，同时这个整数需要满足其各个位数上的数字是单调递增。
// （当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。）

// 暴露接口
const monotoneIncreasingDigits = function (N: number): number {
    const strNumArr: string[] = N.toString().split(''); // 转换为字符串数组
    // 开始从第二位检查字符串数组
    for (let i = 1; i < strNumArr.length; i++) {
        if (strNumArr[i] < strNumArr[i - 1]) {
            let currIndex: number = i - 1; // 当前扫描索引
            // 找到从哪里开始变0
            do {
                strNumArr[currIndex] = (parseInt(strNumArr[currIndex], 10) - 1).toString();
                currIndex--;
            } while (currIndex >= 0 && strNumArr[currIndex] > strNumArr[currIndex + 1]);
            // 此时的currIndex已经指向安全位置，currIndex + 1是退位位置，currIndex + 2是需要变9的位置
            // 构造字符串，从currIndex开始填9
            return monotoneIncreasingDigits_build(strNumArr, currIndex + 2)
        }
    }
    // 经过校验则直接返回
    return N;
};
// 构造相应字符串，填9
function monotoneIncreasingDigits_build(strArr: string[], index: number): number {
    // 对应位数后面全部填9
    for (let i = index; i < strArr.length; i++) {
        strArr[i] = '9';
    }
    return parseInt(strArr.join(''), 10);
}


// 这道题目的难度尚可，对长数字处理不方便的话可以转换为字符数组来处理会简单很多
// 这道题的解题关键在于需要在纸上多手写几个例子，搞懂单调递增的数字到底怎么求
// 首先我们需要扫描原数字位数，找到第一个小于前一个数位的位置（当然也有可能不存在，那说明原数就是单调递增的）
// 找到之后这个位置包括其后面的所有数其实都应该是9了（满足贪心思想，因为前面一个数位必定需要退位）
// 但这里又有额外情况，可能前面的数位退位以后就不满足前面的单调递增了，例如 776 变成了 766
// 这个时候我们需要让前一位再退1位，知道满足单调递增或没有位置可退了，如666，此时记录下退位位置
// 我们从退位位置 + 1开始直到结束位置填9，即得699，此时就满足了题目要求，转换为数字返回即可。